package com.dyz.leetcode._11_comprehensiveApplication;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class _350_intersect {
    //哈希查找
    public int[] intersect(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<>();
        for(int num:nums2){
            map.put(num, map.getOrDefault(num, 0)+1);
        }
        int[] res = new int[Math.min(nums1.length, nums2.length)];
        int index = 0;
        for(int num : nums1){
            if(map.containsKey(num) && map.get(num)>0){
                res[index++] = num;
                map.put(num, map.get(num)-1);
            }
        }
        return Arrays.copyOfRange(res, 0, index);
    }
    // 双指针
    // 时间复杂度：O(mlogm + nlogn)
    // 空间复杂度：O(m + n)
    public int[] intersect1(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);

        int[] res = new int[Math.min(nums1.length, nums2.length)];
        int i = 0;
        int j = 0;
        int index = 0;
        while (i<nums1.length && j< nums2.length){
            if(nums1[i]==nums2[j]){
                res[index++] = nums1[i];
                i++;
                j++;
            }else if(nums1[i]<nums2[j]){
                i++;
            }else {
                j++;
            }
        }
        return Arrays.copyOfRange(res, 0, index);
    }

    // 二分
    // 时间复杂度：O(mlogm + nlogn)
    // 空间复杂度：O(m + n)
    public int[] intersect2(int[] nums1, int[] nums2) {
        Arrays.sort(nums1);
        Arrays.sort(nums2);

        int[] res = new int[Math.min(nums1.length, nums2.length)];
        int i = 0;

        int index = 0;
        while (i<nums1.length ){
            int lowerBound = searchFirstTargetIndex(nums2, nums1[i]);
            if(lowerBound==-1){
                i++;
                continue;
            }
            int count=0;
            while (lowerBound<nums2.length && nums2[lowerBound] == nums1[i]){
                count++;
                lowerBound++;
            }
            //在nums1中找到相同的元素的个数
            int j = i;
            while (j<nums1.length && nums1[j]==nums1[i]){
                j++;
                if(count>0){
                    res[index++] = nums1[i];
                    count--;
                }
            }
            i=j;
        }
        return Arrays.copyOfRange(res, 0, index);
    }

    private int searchFirstTargetIndex(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (target > nums[mid]) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        if (nums[left] == target) {return left;}
        return -1;
    }
}
